#include "classical-problems.h"

#include <algorithm>

namespace pot {
template<typename T>
inline T *Next(T *p) {
  return ++p;
}

template<typename T>
struct ListNode {
  T val;
  ListNode *next;
};

template<typename T>
inline ListNode<T> *Next(ListNode<T> *node) {
  return node->next;
};

template<typename T>
void QuickSort(T s, T e) {
}

// make sure n > 0
size_t Split1(int *A, size_t n) { 
  int tmp = A[0];
  int left = 1, right = n - 1;
  while (left < right) {
    while (left < right && A[left] <= tmp) ++left;

    // if left == right, A[left] can be any case
    // else A[left] > tmp
    while (left < right && A[right] >= tmp) --right;
    // if left == right, A[left] can be any case
    // else A[right] < tmp, A[left] > tmp;

    std::swap(A[left], A[right]);
    // if left == right, A[left] and A[right] can be any case
    // else A[right] > tmp, A[left] < tmp;
    ++left;
  }
  
  // if left > right, A[left] >= tmp, A[right] can be any case
  // else if left == right, A[left] > tmp, A[right] > tmp;

  // in total A[left] >= tmp
  if (A[right] < tmp) {
    A[0] = A[right];
    A[right] = tmp;
  }
  return right;
}

// make sure n > 0
size_t Split2(int *A, size_t n) { 
  int tmp = A[0];
  int left = 1, right = n - 1;
  while (left < right) {
    while (left < right && A[left] <= tmp) ++left;
    
    while (left < right && A[right] >= tmp) --right;

    int det = right - left;
    
    if (det == 0) break;
    
    std::swap(A[left], A[right]);

    ++left;
    if (det > 1) --right;
  }
  if (A[left] < tmp) {
    A[0] = A[left];
    A[left] = tmp;
  }
  return left;
}

typedef size_t (*SPLIT)(int *, size_t);

template<typename SPLIT split>
void QuickSort(int *A, size_t n) {
  if (n < 2) return;

  size_t p = split(A, n); 

  QuickSort<split>(A, p);
  QuickSort<split>(A + p, n - p);
}

void QuickSort1(int *A, size_t n) {
  QuickSort<Split1>(A, n);
}

void QuickSort2(int *A, size_t n) {
  QuickSort<Split2>(A, n);
}

int MidOfThree(int *A, size_t l, size_t r) {
  int mid = (l + r) >> 1;
  if (A[l] < A[mid]) {
    if (A[mid] <= A[r]) return mid;
    if (A[l] >= A[r]) return l;
    return r;
  }
  else if (A[l] > A[mid]) {
    if (A[mid] >= A[r]) return mid;
    if (A[l] <= A[r]) return l;
    return r;
  }
  return mid;
}

int RandPivot(size_t l, size_t r) {
  return rand() % (r - l + 1) + l;
}

size_t Split3(int *A, size_t l, size_t r) {
  int pivot = l;// MidOfThree(A, l, r);
  int pivot_val = A[pivot];
  //A[pivot] = A[l];
  while (l < r) {
    while (l < r && A[r] >= pivot_val) --r;
    A[l] = A[r];

    while (l < r && A[l] <= pivot_val) ++l;

    A[r] = A[l];
  }
  A[l] = pivot_val;
  return l;
}

void QuickSort3(int *A, size_t l, size_t r) {
  if (l >= r) return;

  size_t p = Split3(A, l, r);
  if (p > l) QuickSort3(A, l, p - 1);
  if (p < r) QuickSort3(A, p + 1, r);
}

void InsertionSort(int *A, int l, int r) {
  for (int i = l + 1; i <= r; ++i) {
    int tmp = A[i];
    size_t j = i - 1;
    while (j >= l && A[j] > tmp) {
      A[j + 1] = A[j];
      --j;
    }
    // A[k] <= tmp, for k = 0, ..., j
    A[j + 1] = tmp;
  }
}

void QuickSort4(int *A, int l, int r) {
  //if (l >= r) return;
  // accelerate a little when size is not too big
  while (r - l > 16) {
    size_t p = Split3(A, l, r);
    QuickSort4(A, p + 1, r);
    r = p - 1;
  }
  InsertionSort(A, l, r);
}

inline int log2(int n) {
  int h = 0;
  while (n > 0) {
    ++h;
    n >>= 1;
  }
  return h;
}

inline size_t FirstSon(size_t p) { return (p << 1) + 1; }

void SiftDown(int A[], size_t p, size_t n) {  
  for (size_t k = FirstSon(p); k < n; p = k, k = FirstSon(p)) {    
    if (k + 1 < n && A[k] < A[k + 1]) ++k;    
    
    if (A[k] <= A[p]) break;
    std::swap(A[k], A[p]);    
  }
}

void SiftUp(int A[], size_t i) {  
  while (i > 0) {
    size_t p = (i - 1) >> 1;
    if (A[p] < A[i]) std::swap(A[i], A[p]);
    i = p;
  }
}

void HeapSort(int A[], size_t n) {
  // O(n)
  for (int p = (n - 1) / 2; p >= 0; --p) {
    pot::SiftDown(A, p, n);
  }
  // O(nlogn)
  /*for (size_t i = 1; i < n; ++i) {
    pot::SiftUp(A, i);
  }*/

  for (size_t i = n - 1; i > 0; --i) {
    std::swap(A[i], A[0]);
    pot::SiftDown(A, 0, i);
  }
}


inline void IntroSort(int *A, int l, int r, int d) {
  if (l > r) return;

  if (d-- < 3) {    
    pot::HeapSort(A + l, r - l + 1);
    return;
  }  
   //if (l >= r) return;
  // accelerate a little when size is not too big
  while (r - l > 16) {
    size_t p = Split3(A, l, r);
    IntroSort(A, p + 1, r, d);
    r = p - 1;
  }
  InsertionSort(A, l, r);
}

void IntroSort(int *A, size_t l, size_t r) {
  int depth = log2(r - l + 1);
  IntroSort(A, l, r, depth);
}

void Check(int *A, int *B, int n) {
  for (int i = 0; i < n; ++i) {
    if (A[i] != B[i]) {
      printf("error\n");
      return;
    }
  }
  printf("success\n");
}

int *CopyData(int *A, int n) {
  int *B = new int[n];
  memcpy(B, A, sizeof(int) * n);
  return B;
}

void SortTest() {
  const int n = 1000000;
  int *A = new int[n];
  
  pot::GenSignedIntegers(A, n);  

  int *B = pot::CopyData(A, n);
  int *C = pot::CopyData(A, n);
  int *D = pot::CopyData(A, n);
  int *E = pot::CopyData(A, n);
  int *F = pot::CopyData(A, n);

  clock_t t[7];
  t[0] = clock();
  std::sort(A, A + n);  
  t[1] = clock();
  pot::QuickSort1(B, n);  
  t[2] = clock();
  pot::QuickSort2(C, n);
  t[3] = clock();
  pot::QuickSort3(D, 0, n - 1);
  t[4] = clock();
  pot::IntroSort(F, 0, n - 1);
  t[5] = clock();
  pot::HeapSort(E, n);
  t[6] = clock();
  
  Check(A, B, n);
  Check(A, C, n);
  Check(A, D, n);
  Check(A, E, n);
  Check(A, F, n);

  const char *kNames[] = { "STL", "QuickSort1", "QuickSort2", "QuickSort3", "QuickSort4", "HeapSort" };
  for (int i = 0; i < 6; ++i) {
    double eps = (t[i + 1] - t[i]) / 1000.0;
    printf("%s, time: %f\n", kNames[i], eps);
  }

  //pot::Print(A, n);
  //pot::Print(B, n);

  delete[] A;
  delete[] B;
  delete[] C;
  delete[] D;
  delete[] E;
  delete[] F;
}

} // pot